// 经典的二分搜索算法，机制类似于indexOf

// 经典二分查找实现
export function binarySearch(sortedArr: number[], target: number): number {
    // 搜索的区间为左闭右闭
    let left = 0;
    let right = sortedArr.length - 1;
    // 当区间出现交叉时，进行二分搜索
    while (left <= right) {
        const mid = left + Math.floor((right - left + 1) / 2);// 记得要加上left
        if (sortedArr[mid] === target) {// 元素相等时，直接返回索引
            return mid;
            // 否则根据大小情况来砍区间
        } else if (sortedArr[mid] < target) {
            left = mid + 1;
        } else if (sortedArr[mid] > target) {
            right = mid - 1;
        }
    }
    // 都没找到即返回 -1
    return -1;
}


// 测试用例
console.log(binarySearch([1, 2, 3, 4, 5, 6, 7, 8, 9], 9));// 8
console.log(binarySearch([1, 2, 3, 4, 5, 6, 7, 8], 1)); // 0
console.log(binarySearch([1, 2, 3, 4, 5, 6, 7, 8, 9], 5));// 4
console.log(binarySearch([1, 2, 3, 4, 5, 6, 7, 8, 9], 10)); // -1
console.log(binarySearch([1, 2, 3, 4, 5, 6, 7, 8, 9], -3)); // -1
console.log(binarySearch([1], -3));// -1
